#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/6/11 21:28
# @USER    : Shengji He
# @File    : CombinationSum.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from typing import List


class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        """
        Given a set of candidate numbers (candidates) (without duplicates) and a target number (target),
        find all unique combinations in candidates where the candidate numbers sums to target.

        The same repeated number may be chosen from candidates unlimited number of times.

        Note:
            - All numbers (including target) will be positive integers.
            - The solution set must not contain duplicate combinations.
        Example 1:
            Input: candidates = [2,3,6,7], target = 7,

            A solution set is:

            [
              [7],

              [2,2,3]
            ]

        Example 2:
            Input: candidates = [2,3,5], target = 8,

            A solution set is:

            [

              [2,2,2,2],

              [2,3,3],

              [3,5]

            ]

        :param candidates: List[int]
        :param target: int
        :return: List[List[int]]
        """
        candidates.sort()
        ls = 0
        ans = []
        while ls < len(candidates) and candidates[ls] <= target:
            div, res = divmod(target, candidates[ls])
            while div > 0:
                temp = [candidates[ls]] * div
                if res == 0:
                    ans.append(temp)
                elif res > candidates[ls]:
                    output = self.combinationSum(candidates[ls + 1:], res)
                    if not output:
                        pass
                    else:
                        for ele in output:
                            ans.append(temp + ele)
                else:
                    pass
                div -= 1
                res = target - candidates[ls] * div
            ls += 1
        return ans


if __name__ == '__main__':
    S = Solution()
    nums = [2, 3, 5]
    target = 8
    # nums = [2, 3, 6, 7]
    # target = 7
    print(S.combinationSum(nums, target))
    print('done')
